מבני נתונים אלמנטריים:

• מידע שמור בזיכרון. תא זיכרון מכיל ערך בודד, אליו אפשר להיכנס בזמן קבוע.

• ניתן להשתמש במספר תאים ברצף.

• ניתן גם לקשר בין תאים באמצעות מצביעים.

• המבנים האלמנטרים הבסיסיים:

  • מערך:
    • בנוי מתאי זיכרון רציפים
    • תומך בפעולות הבאות:
      • בניית מערך בגודל קבוע (סיבוכיות $\mathrm{\Theta }(1)$).
      • גישה לאלמנט (סיבוכיות $\mathrm{\Theta }(1)$).
  • רשימה מקושרת:
    • בנוי מתאי זיכרון מפוזרים, אשר מקושרים ביניהם באמצעות מצביעים
    • תומכת בפעולות הבאות:
      • יצירת רשימה ריקה.
      • גישה לאלמנטים לפי סדר הרשימה.
      • הכנסה של אלמנט חדש.
      • מחיקה של אלמנט.
    • ברשימה מקושרת רגילה לכל אלמנט יש מצביע לאלמנט הבא
    • ברשימה מקושרת דו כיוונית לכל אלמנט יש מצביע לאלמנט הבא והקודם.

• סנטינל:

  • חוליה שנוצרת עם המבנה ולא מכילה נתונים.
  • ברשימה מקושרת הסנטינל היא הראש (L.head) אשר מצביע על האיבר הראשון (באמצעות L.next) (שמצביע עליה בחזרה ברשימה דו כיוונית). האיבר האחרון מצביע עליו (באמצעות L.next) (והוא מצביע עליו בחזרה ברשימה דו כיוונית באמצעות L.prev).
  • 

• מבנה עץ:

  • מבנה המתאר היררכיה בין איברים במבנה
  • האיברים בעץ נקראים קודקודים (nodes) או צמתים. כאשר יש קודקודים מיוחדים:
    • שורש: האב הקדמון של כל מי שמתחתיו.
    • עלים: קודקודים בלי ילדים.
    • אב ובן: אב הוא מי שנמצא מעל בנו, בן הוא מי שנמצא מתחת לאב.
    • קודקוד פנימי: קודקוד שהוא לא עלה.
  • תת עץ:
    • הקודקוד שמתחיל את תת העץ הופך לשורש וכל הצאצאים שלו הופכים לקודקודים.
  • עומק:
    • מספר הצעדים שצריך לעשות מקודקוד עד שמגיעים לשורש.
    • עומק של שורש הוא 0.
  • גובה:
    • מספר הצעדים שצריך לעשות מקודקוד לעלה הכי נמוך.
    • גובה של עלה הוא 0.
  • דרגה:
    • מספר הבנים של אותו קודקוד.
    • קודקוד ללא בנים הוא בעל דרגה 0.
    • מכאן ניתן להגדיר שעלה הוא בעל דרגה 0.

מבני נתונים אבסטרקטיים (ADT):

• מתחלק לשני חלקים:

  • הגדרת טיפוס הנתונים המופשט:
    • מה הערכים שיש לאחסן.
    • אוסף הפעולות על הנתונים בהן יש לתמוך.
    • רעיון מופשט ללא מימוש.
  • מימוש טיפוס הנתונים המופשט:
    • מגדיר כיצד הנתונים ישמרו בזיכרון.
    • מגדיר את האלגוריתמים למימוש הפעולות הנדרשות.
    • ניתן לממש מבנה נתונים מופשט על ידי סוגים שונים של מבני נתונים אלמנטרים, ומבנה נתונים אלמנטרי יכול לממש סוגים שונים של מבני נתונים אבסטרקטים, לכן יש יותר מדרך מימוש אחת.
      • לדוגמא: תור / מחסנית ניתן לממש בתור מערך / רשימה מקושרת.

• מבנה מחסנית:

  • אוסף של איברים שמסוגל לבצע את הפעולות הבאות:
    • פעולת create: יצירת מבנה מחסנית ריקה.
    • פעולת isEmpty(S): מחזיר בוליאני לפי אם המחסנית S ריקה.
    • פעולת push(S, x): הוספת איבר x למחסנית S.
    • פעולת pop(S): קבלת האיבר האחרון שהוכנס והוצאתו מהמחסנית.
  • הסיבוכיות עבור מחסנית אשר ממומשת באמצעות רשימה מקושרת:
    • סיבוכיות מקום $\mathrm{\Theta }(n)$
    • פעולות אלמנטריות (create, isEmpty, pop, push): $\mathrm{\Theta }1$

• מבנה תור:

  • אוסף של איברים שמסוגל לבצע את הפעולות הבאות:
    • פעולת create: יצירת מבנה תור ריק.
    • פעולת isEmpty(Q): מחזיר בוליאני לפי אם התור S ריק.
    • פעולת enqueue(Q, x): הוספת איבר x לתור S.
    • פעולת dequeue(Q): קבלת האיבר הראשון שהוכנס והוצאתו מהתור.

• מבנה Dynamic set ADT:

  • מכיל את השדות:
    • שדה key: ערך חד חד ערכי המייצג את האיבר
    • שדה data: מידע נוסף שמאוחסן באיבר
  • מכיל את הפעולות:
    • פעולת Search(S,k): חיפוש של איבר בעל מפתח k בסט S.
    • פעולת Insert(S,x): הכנסת איבר X לסט S.
    • פעולת Delete(S,x): מחיקת איבר לפי המצביע על המקום שלו בסט.
    • פעולת minimum(S): מחזירה מהסט מי האיבר עם המפתח המינימלי.
    • פעולת Maximum(S): מחזירה מהסט מי האיבר עם המפתח המקסימלי.
    • פעולת Successor(S,x): מחזירה את האיבר הכי קטן בין כל האיברים הגדולים מהאיבר X.
    • פעולת Predecessor(S,x): פעולה הופכית ל Successor.

תובנות מהתרגול:

• סיבוכיות מימוש:

  • מדד מתמטי של משאבי המערכת הנחוצים לפתרון בעיה נתונה באמצעות מחשב. המשאבים העיקריים הם:
    • סיבוכיות זמן: זמן הריצה הנחוץ לשם ביצוע האלגוריתם.
    • סיבוכיות מקום: כמות הזיכרון הנחוץ לשם ביצוע האלגוריתם.
    • בדכ יהיה trade-off בין סיבוכיות הזמן וסיבוכיות המקום, כאשר החשוב מביניהם למשימה מסוימת יהיה מי שיכריע.
  • אם לא נאמר אחרת, תמיד נעריך את הביצוע עבור המקרה הגרוע ביותר כפונקציה של גודל הקלט.

• מרכיבי פתרון מלא של בעיות למימוש:

  • תיאור של מבני הנתונים הנדרשים למימוש, שימושם והשינויים שבוצעו בהם שלא תוארו בהרצאות / תרגולים.
  • תיאור של האלגוריתמים המממשים כל פעולה בה תומך ה - ADT. את האלגוריתם נכתוב בצורה מילולית (ולא כקוד).
  • ניתוח זמן ריצת האלגוריתמים והזיכרון הנוסף הנדרש.

• שיטת פתרון:

  • נתחיל תמיד ממציאת הפתרון הנאיבי - הוא הפתרון הפשוט ביותר.
  • נסתכל על ה-ADT והדרישות, וננסה להבין מה הפתרון הנאיבי עושה טוב ומה הוא עושה לא טוב. מכך נבין איך ניתן לשפר את הפתרון כדי ליצור פתרון לא נאיבי.
  • נוודא שהפתרון מחזיר את התשובה הנכונה שעומדת בכלל דרישות הזמן והמקום בכל המקרים.